package leetcode.editor.day;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

// 1282 用户分组
class GroupThePeopleGivenTheGroupSizeTheyBelongTo {
    public static void main(String[] args) {
        Solution solution = new GroupThePeopleGivenTheGroupSizeTheyBelongTo().new Solution();
        solution.groupThePeople(new int[]{3, 3, 3, 3, 3, 1, 3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://leetcode.cn/problems/group-the-people-given-the-group-size-they-belong-to/solution/by-tong-zhu-89og/
        // 方法一：hash表
        // 方法二：数组代替hash表
        // 方法三：从大到小排序，直接取固定大小（贪心）
        public List<List<Integer>> groupThePeople(int[] groupSizes) {
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            List<List<Integer>> res = new LinkedList<>();

            for (int i = 0; i < groupSizes.length; i++) {
                int groupSize = groupSizes[i];
                map.putIfAbsent(groupSize, new LinkedList<>());

                if (map.get(groupSize).size() >= groupSize) {
                    res.add(new LinkedList<>(map.get(groupSize)));
                    map.get(groupSize).clear();
                }

                map.get(groupSize).add(i);
            }

            for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
                res.add(entry.getValue());
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
